Search for: All records

This work proposes a rigorous and practical algorithm for quad-mesh generation based the Abel-Jacobi theory of algebraic \textcolor{red}{curves}. We prove sufficient and necessary conditions for a flat metric with cone singularities to be compatible with a quad-mesh, in terms of the deck-transformation, then develop an algorithm based on the theorem. The algorithm has two stages: first, a meromorphic quartic differential is generated to induce a T-mesh; second, the edge lengths of the T-mesh are adjusted by solving a linear system to satisfy the deck transformation condition, which produces a quad-mesh. In the first stage, the algorithm pipeline can be summarized as follows: calculate the homology group; compute the holomorphic differential group; construct the period matrix of the surface and Jacobi variety; calculate the Abel-Jacobi map for a given divisor; optimize the divisor to satisfy the Abel-Jacobi condition by integer programming; compute \textcolor{red}{a} flat Riemannian metric with cone singularities at the divisor by Ricci flow; \textcolor{red}{isometrically} immerse the surface punctured at the divisor onto the complex plane and pull back the canonical holomorphic differential to the surface to obtain the meromorphic quartic differential; construct a motorcycle graph to generate a T-Mesh. In the second stage, the deck transformation constraints are formulated as a linear equation system of the edge lengths of the T-mesh. The solution provides a flat metric with integral deck transformations, which leads to the final quad-mesh. The proposed method is rigorous and practical. The T-mesh and quad-mesh results can be applied for constructing Splines directly. The efficiency and efficacy of the proposed algorithm are demonstrated by experimental results on surfaces with complicated topologies and geometries. 

An optimal transportation map finds the most economical way to transport one probability measure to the other. It has been applied in a broad range of applications in vision, deep learning and medical images. By Brenier theory, computing the optimal transport map is equivalent to solving a Monge-Amp\`ere equation. Due to the highly non-linear nature, the computation of optimal transportation maps in large scale is very challenging. This work proposes a simple but powerful method, the FFT-OT algorithm, to tackle this difficulty based on three key ideas. First, solving Monge-Amp\`ere equation is converted to a fixed point problem; Second, the obliqueness property of optimal transportation maps are reformulated as Neumann boundary conditions on rectangular domains; Third, FFT is applied in each iteration to solve a Poisson equation in order to improve the efficiency. Experiments on surfaces captured from 3D scanning and reconstructed from medical imaging are conducted, and compared with other existing methods. Our experimental results show that the proposed FFT-OT algorithm is simple, general and scalable with high efficiency and accuracy. 

Optimal transportation finds the most economical way to transport one probability measure to another, and it plays an important role in geometric modeling and processing. In this paper, we propose a moving mesh method to generate adaptive meshes by optimal transport. Given an initial mesh and a scalar density function defined on the mesh domain, our method will redistribute the mesh nodes such that they are adapted to the density function. Based on the Brenier theorem, solving an optimal transportation problem is reduced to solving a Monge-Amp\`ere equation, which is difficult to compute due to the high non-linearity. On the other hand, the optimal transportation problem is equivalent to the Alexandrov problem, which can finally induce an effective variational algorithm. Experiments show that our proposed method finds the adaptive mesh quickly and efficiently. 

Optimal transportation maps play fundamental roles in many engineering and medical fields. The computation of optimal transportation maps can be reduced to solve highly non-linear Monge-Ampere equations. This work summarizes the geometric variational frameworks for spherical optimal transportation maps, which offers solutions to the Minkowski problem in convex differential geometry, reflector design and refractor design problems in optics. The method is rigorous, robust and efficient. The algorithm can directly generalized to higher dimensions. 

Optimal transportation (OT) finds the most economical way to transport one measure to another and plays an important role in geometric modeling and processing. Based on the Brenier theorem, the OT problem is equivalent to the Alexandrov problem, which is the dual to the Pogorelov problem. Although solving the Alexandrov/Pogorelov problem are both equivalent to solving the Monge-Amp\`{e}re equation, the former requires second type boundary condition and the latter requires much simpler Dirichlet boundary condition. Hence, we propose to use the Pogorelov map to approximate the OT map. The Pogorelov problem can be solved by a convex geometric optimization framework, in which we need to ensure the searching inside the admissible space. In this work, we prove the discrete Alexandrov maximum principle, which gives an apriori estimate of the searching. Our experimental results demonstrate that the Pogorelov map does approximate the OT map well with much more efficient computation. 

Biomarkers play an important role in early detection and intervention in Alzheimer’s disease (AD). However, obtaining effective biomarkers for AD is still a big challenge. In this work, we propose to use the worst transportation cost as a univariate biomarker to index cortical morphometry for tracking AD progression. The worst transportation (WT) aims to find the least economical way to transport one measure to the other, which contrasts to the optimal transportation (OT) that finds the most economical way between measures. To compute the WT cost, we generalize the Brenier theorem for the OT map to the WT map, and show that the WT map is the gradient of a concave function satisfying the Monge-Ampere equation. We also develop an efficient algorithm to compute the WT map based on computational geometry. We apply the algorithm to analyze cortical shape difference between dementia due to AD and normal aging individuals. The experimental results reveal the effectiveness of our proposed method which yields better statistical performance than other competiting methods including the OT. 

Shape analysis has been playing an important role in early diagnosis and prognosis of neurodegenerative diseases such as Alzheimer's diseases (AD). However, obtaining effective shape representations remains challenging. This paper proposes to use the Alexandrov polyhedra as surface-based shape signatures for cortical morphometry analysis. Given a closed genus-0 surface, its Alexandrov polyhedron is a convex representation that encodes its intrinsic geometry information. We propose to compute the polyhedra via a novel spherical optimal transport (OT) computation. In our experiments, we observe that the Alexandrov polyhedra of cortical surfaces between pathology-confirmed AD and cognitively unimpaired individuals are significantly different. Moreover, we propose a visualization method by comparing local geometry differences across cortical surfaces. We show that the proposed method is effective in pinpointing regional cortical structural changes impacted by AD. 

Optimal transportation (OT) maps play fundamental roles in many engineering and medical fields. The computation of optimal transportation maps can be reduced to solve highly non-linear Monge-Ampere equations. In this work, we summarize the geometric variational framework to solve optimal transportation maps in Euclidean spaces. We generalize the method to solve worst transportation maps and discuss about the symmetry between the optimal and the worst transportation maps. Many algorithms from computational geometry are incorporated into the method to improve the efficiency, the accuracy and the robustness of computing optimal transportation.